/*
 * @Author: czy
 * @Date: 2021-07-09 15:00:40
 * @LastEditTime: 2021-07-11 21:46:18
 */
#ifndef __MAP_H_
#define __MAP_H_

#include "sys/container.h"

#define container_of(ptr, type, member) ({			\
        const typeof( ((type *)0)->member ) *__mptr = (ptr);	\
        (type *)( (char *)__mptr - offsetof(type,member) ); })
#define offsetof(TYPE, MEMBER) ((int)&((TYPE *)0)->MEMBER)
#define NULL ((void *)0)
#define RB_RED 0
#define RB_BLACK 1

#define rb_parent(r) ((Node *)((r)->rb_parent_color & ~3))
#define rb_color(r) ((r)->rb_parent_color & 1)
#define rb_is_red(r) (!rb_color(r))
#define rb_is_black(r) rb_color(r)
#define rb_set_red(r)               \
	do                              \
	{                               \
		(r)->rb_parent_color &= ~1; \
	} while (0)
#define rb_set_black(r)            \
	do                             \
	{                              \
		(r)->rb_parent_color |= 1; \
	} while (0)

static inline void rb_set_parent(Node *rb, Node *p)
{
	rb->rb_parent_color = (rb->rb_parent_color & 3) | (unsigned long)p;
}
static inline void rb_set_color(Node *rb, int color)
{
	rb->rb_parent_color = (rb->rb_parent_color & ~1) | color;
}

#define rb_entry(ptr, type, member) container_of(ptr, type, member)

#define RB_EMPTY_ROOT(root) ((root)->rb_node == NULL)
#define RB_EMPTY_NODE(node) (rb_parent(node) == node)
#define RB_CLEAR_NODE(node) (rb_set_parent(node, node))

static inline void rb_init_node(Node *rb)
{
	rb->rb_parent_color = 0;
	rb->rb_right = (Node *)NULL;
	rb->rb_left = (Node *)NULL;
	RB_CLEAR_NODE(rb);
}

void rb_erase(Node *, Map *);

typedef void (*rb_augment_f)(Node *node, void *data);

void rb_augment_insert(Node *node,
					   rb_augment_f func, void *data);
Node *rb_augment_erase_begin(Node *node);
void rb_augment_erase_end(Node *node,
						  rb_augment_f func, void *data);

/* Fast replacement of a single node without remove/rebalance/add/rebalance */
void rb_replace_node(Node *victim, Node *newnode,
					 Map *root);

static inline void rb_link_node(Node *node, Node *parent,
								Node **rb_link)
{
	node->rb_parent_color = (unsigned long)parent;
	node->rb_left = node->rb_right = (Node *)NULL;

	*rb_link = node;
}

#endif